/**
* FileName: AdjacencyMatrixGraph.c
 * ---------------------------------------------------------------------------------------------------------------------
 * Program 17.3 Graph ADT implementation (adjacency matrix)
 * ---------------------------------------------------------------------------------------------------------------------
 * This implementation of the interface in Program 17.1 uses a two-dimensional array.
 *
 * An implementation of the function `MATRIXinit`, which allocates memory for the array and initializes it,
 * is given in Program 17.4.
 *
 * The rest of the code is straightfor-ward: An edge `i-j` is present in the graph if and only if
 * `a[i][j]` and `a[j][i]` are both 1.
 *
 * Edges are inserted and removed in constant time, and duplicate edges are silently ignored.
 *
 * Initialization and extracting all edges each take time proportional to $V^2$.
 *
 *
 */
#include <stdio.h>
#include <stdlib.h>

//边相关
typedef struct {
    int v;
    int w;
}
Edge;

//图相关
typedef struct graph *Graph;
struct graph {
    int V;
    int E;
    int** adj;
};

//辅助函数声明
int** MATRIXinit(int, int, int);
Edge EDGE(int, int);
void GRAPHshow(Graph);

//图操作声明
Graph GRAPHinit(int);
void GRAPHinsertE(Graph, Edge);
void GRAPHremoveE(Graph, Edge);
int GRAPHedges(Edge [], Graph);
Graph GRAPHcopy(Graph);
void GRAPHdestroy(Graph);

//辅助函数实现
/**
 * Program 17.4 Adjacency-matrix allocation and initialization
 * -------------------------------------------------------------------------------------------------------------
 * This program uses the standard C array-of-arrays representation for the two-dimensional adjacency matrix (see Section 3.7).
 * It allocates `r` rows with `c` integers each, then initializes all entries to the value `val`.
 *
 * The call `MATRIXinit(V, V, 0)` in Program 17.3 takes time proportional to $V^2$ to create a matrix that
 * represents a V-vertex graph with no edges.
 *
 * For small $V$, the cost of $V$ calls to `malloc` might predominate.
 */
int** MATRIXinit(int r, int c, int val) {
    int i;
    int j;
    int** t = malloc(r * sizeof(int*));
    for (i = 0; i < r; i++) {
        t[i] = malloc(c * sizeof(int));
    }
    for (i = 0; i < r; i++) {
        for (j = 0; j < c; j++) {
            t[i][j] = val;
        }
    }
    return t;
}

Edge EDGE(int v, int w) {
    Edge edge;
    edge.v = v;
    edge.w = w;
    return edge;
}

void GRAPHshow(Graph G) {
    int i;
    int j;
    printf("%d vertices, %d edges\n", G->V, G->E);

    //邻接列表
    for (i = 0; i < G->V; i++) {
        printf("%2d:", i);
        for (j = 0; j < G->V; j++) {
            if (G->adj[i][j] == 1) {
                printf(" %2d", j);
            }
        }
        printf("\n");
    }
    // //邻接矩阵
    // for (i = 0; i < G->V; i++) {
    //     printf("%2d:", i);
    //     for (j = 0; j < G->V; j++) {
    //         printf(" %2d", G->adj[i][j]);
    //     }
    //     printf("\n");
    // }
}

//图操作函数实现
Graph GRAPHinit(int V) {
    Graph G = malloc(sizeof(*G));
    G->V = V;
    G->E = 0;
    G->adj = MATRIXinit(V, V, 0);
    return G;
}

void GRAPHinsertE(Graph G, Edge e) {
    int v = e.v;
    int w = e.w;
    if (G->adj[v][w] == 0) {
        G->E++;
    }
    G->adj[v][w] = 1;
    G->adj[w][v] = 1;
}

void GRAPHremoveE(Graph G, Edge e) {
    int v = e.v;
    int w = e.w;
    if (G->adj[v][w] == 1) {
        G->E--;
    }
    G->adj[v][w] = 0;
    G->adj[w][v] = 0;
}
int GRAPHedges(Edge a[], Graph G) {
    int v;
    int w;
    int E = 0;
    for (v = 0; v < G->V; v++) {
        for (w = v+1; w < G->V; w++) {
            if (G->adj[v][w] == 1) {
                a[E++] = EDGE(v, w);
            }
        }
    }
    return E;
}
Graph GRAPHcopy(Graph);
void GRAPHdestroy(Graph);
